package top.drose;

import org.jetbrains.annotations.NotNull;

//这两页的两个函数
public class P44_P45 {

    //找x的后驱（最接近的比x大的数字）
    int bin_search(@NotNull int a[], int x){
        int left=0,right=a.length;//不是左闭右开
        //因为并不会
        while(left<right){
            int mid=left+(right-left)/2;
            if(a[mid]>=x){
                right=mid;
            }
            else{
                left=mid+1;
            }
        }
        return left;
    }

    //找x的前驱
    int bin_search2(int a[],int x){
        int left=0,right=a.length;
        while(left<right){
            //这里有+1，叫做右中位数，上面那个叫左中位数
            int mid=left+(right-left+1)/2;
            if(a[mid]<=x){
                left=mid;
            }else{
                right=mid-1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        //下表从0到8
        int res=new P44_P45().bin_search(new int[]{1,2,3,4,5,6,7,8,9},10);
        //如果找不到，则下表是越界的
        System.out.printf("%d",res);

    }
}
